package mo.tags.graph;

import java.util.ArrayList;
import java.util.List;

public class L207 {

    private List<List<Integer>> edges;
    private int[] visited;
    private boolean valid = true;

    public boolean canFinish(int numCourses, int[][] prerequisites) {
        edges = new ArrayList<>(numCourses);
        for (int i = 0; i < numCourses; i++) {
            edges.add(new ArrayList<>());
        }
        visited = new int[numCourses];
        for (int[] require : prerequisites) {
            edges.get(require[1]).add(require[0]);
        }

        for (int i = 0; i < numCourses && valid; i++) {
            if (visited[i] == 0) {
                dfs(i);
            }
        }

        return valid;
    }


    private void dfs(int index) {
        visited[index] = 1;
        List<Integer> targets = edges.get(index);
        for (int t : targets) {
            if (visited[t] == 0) {
                dfs(t);
            }
            if (!valid) {
                return;
            } else if (visited[t] == 1) {
                valid = false;
                return;
            }
        }
        visited[index] = 2;
    }
}
